{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**23. Merge k Sorted Lists**  <font color=red size=3>_hard_</font>\n",
    "\n",
    "Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.\n",
    "\n",
    "**Example**\n",
    "\n",
    "```\n",
    "Input:\n",
    "[\n",
    "  1->4->5,\n",
    "  1->3->4,\n",
    "  2->6\n",
    "]\n",
    "Output: 1->1->2->3->4->4->5->6\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "1\n",
      "2\n",
      "3\n",
      "4\n",
      "4\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "class ListNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.next = None\n",
    "\n",
    "def min_index(lists):\n",
    "    min = lists[0].val\n",
    "    index = 0;\n",
    "    for i, v in enumerate(lists):\n",
    "        if v.val < min:\n",
    "            min = v.val\n",
    "            index = i\n",
    "    return index\n",
    "\n",
    "def mergeKLists(lists):\n",
    "    \"\"\"\n",
    "    :type lists: List[ListNode]\n",
    "    :rtype: ListNode\n",
    "    \"\"\"\n",
    "    index = min_index(lists)\n",
    "    res = lists[index]\n",
    "    head = res\n",
    "    lists[index] = lists[index].next\n",
    "    while lists:\n",
    "        index = min_index(lists)\n",
    "        head.next = lists[index]\n",
    "        head = head.next\n",
    "        lists[index] = lists[index].next\n",
    "        if lists[index] is None:\n",
    "            del lists[index]\n",
    "    return res\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    node1 = ListNode(1)\n",
    "    node1.next = ListNode(4)\n",
    "    node1.next.next = ListNode(5)\n",
    "\n",
    "    node2 = ListNode(1)\n",
    "    node2.next = ListNode(3)\n",
    "    node2.next.next = ListNode(4)\n",
    "\n",
    "    node3 = ListNode(2)\n",
    "    node3.next = ListNode(6)\n",
    "\n",
    "    result = mergeKLists([node1, node2, node3])\n",
    "\n",
    "    while result.next:\n",
    "        print(result.val)\n",
    "        result = result.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
